//给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 
//
// 算法的时间复杂度应该为 O(log (m+n)) 。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums1 = [1,3], nums2 = [2]
//输出：2.00000
//解释：合并数组 = [1,2,3] ，中位数 2
// 
//
// 示例 2： 
//
// 
//输入：nums1 = [1,2], nums2 = [3,4]
//输出：2.50000
//解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
// 
//
// 
//
// 
//
// 提示： 
//
// 
// nums1.length == m 
// nums2.length == n 
// 0 <= m <= 1000 
// 0 <= n <= 1000 
// 1 <= m + n <= 2000 
// -10⁶ <= nums1[i], nums2[i] <= 10⁶ 
// 
//
// Related Topics 数组 二分查找 分治 👍 6364 👎 0


package leetcode.editor.cn;

// [4]寻找两个正序数组的中位数

public class MedianOfTwoSortedArrays_4 {
    public static void main(String[] args) {
        Solution solution = new MedianOfTwoSortedArrays_4().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int n = nums1.length + nums2.length;
            int m = (n >> 1) - 1;
            int[] arr = merge(nums1, nums2, m);
            if ((n & 1) == 0) {
                return (double) (arr[m] + arr[m + 1]) / 2;
            } else {
                return arr[m + 1];
            }
        }

        public int[] merge(int[] nums1, int[] nums2, int gate) {
            if (nums1.length == 0) {
                return nums2;
            } else if (nums2.length == 0) {
                return nums1;
            }
            int i = 0;
            int j = 0;
            int k = 0;
//            int length = nums1.length + nums2.length;
            int[] arr = new int[gate + 2];
            while (i < nums1.length && j < nums2.length && k <= gate + 1) {
                arr[k++] = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++];
            }
            while (i < nums1.length && k <= gate + 1) {
                arr[k++] = nums1[i++];
            }
            while (j < nums2.length && k <= gate + 1) {
                arr[k++] = nums2[j++];
            }
            return arr;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

    //该方法时间复杂度为O(n+m),不达标！
    class Solution2 {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int[] arr = merge(nums1, nums2);
            int n = nums1.length + nums2.length;
            if ((n & 1) == 0) {
                return (double) (arr[n >> 1] + arr[(n >> 1) - 1]) / 2;
            } else {
                return arr[n >> 1];
            }
        }


        public int[] merge(int[] nums1, int[] nums2) {
            if (nums1.length == 0) {
                return nums2;
            } else if (nums2.length == 0) {
                return nums1;
            }
            int i = 0;
            int j = 0;
            int k = 0;
            int length = nums1.length + nums2.length;
            int[] arr = new int[length];
            while (i < nums1.length && j < nums2.length) {
                arr[k++] = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++];
            }
            while (i < nums1.length) {
                arr[k++] = nums1[i++];
            }
            while (j < nums2.length) {
                arr[k++] = nums2[j++];
            }
            return arr;
        }
    }
}